package main

import "fmt"

//给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
//@url: https://leetcode-cn.com/problems/counting-bits/
//线性时间O(n)、 空间复杂度为O(n)。
//示例 1
//	输入: 2
//	输出: [0,1,1]
//示例 2:
//	输入: 5
//	输出: [0,1,1,2,1,2]
func countBits(num int) []int {
	res := make([]int, num+1)
	for i := 0; i <= num; i++ {
		res[i] = res[i>>1] + (i & 1)
	}
	return res
}
func main() {
	fmt.Printf("%v \n", countBits(2))
	fmt.Printf("%v \n", countBits(5))
}
